package leetcode_core.leetcode_1;

import java.util.ArrayList;
import java.util.List;

public class NSum {
    //注意:调用这个函数之前,nums必须是排好序的
    List<List<Integer>> nSumTarget(int[] nums,int n,int start,long target){
        int size = nums.length;
        List<List<Integer>> ans =  new ArrayList<>();
        //至少是2Sum而且,而且数组大小不能小于n
        if(n<2 || size<n) {
            return ans;
        }
        //base-case
        if(n==2){
            int lo = start ,hi = size-1;
            while(lo < hi){
                long sum = (long)nums[lo] + (long)nums[hi];
                int left = nums[lo];int right = nums[hi];
                if(sum< target){
                    while (lo<hi && nums[lo] == left){
                        lo++;
                    }
                }else if(sum > target){
                    while (lo<hi && nums[hi] == right){
                        hi--;
                    }
                }else {
                    List<Integer> t = new ArrayList<>();
                    t.add(left);t.add(right);
                    while (lo<hi && nums[lo] == left){
                        lo++;
                    }
                    while (lo<hi && nums[hi] == right){
                        hi--;
                    }
                }
            }
        }else{
            //n>2的时候直接递归计算即可
            for(int i = start;i<size;i++){
                List<List<Integer>> tuples = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> tuple : tuples) {
                    tuple.add(nums[i]);
                    ans.add(new ArrayList<>(tuple));
                }
                while (i<size-1 && nums[i] == nums[i+1]){
                    i++;
                }
            }
        }
        return ans;
    }



}
